#pragma once

#include <iostream>

template<typename T, int desiredCapacity=10>
class Queue
{
public:
	Queue();
	Queue(int inDesiredCapacity);
	~Queue();

	int Capacity() const;
	int Size() const;

	void ShowData();

	/**
	 * 队列是否为空
	 * @return 
	 */
	bool IsEmpty() const;

	/**
	 * 队列是否已满
	 * @return 
	 */
	bool IsFull() const;
	
	void Enqueue(T element);
	T Dequeue();
	T Front() const;
	T Rear() const;
private:
	int capacity;
	int size;
	int front;
	int rear;
	T* data;
};

template <typename T, int desiredCapacity>
Queue<T, desiredCapacity>::Queue():
capacity(desiredCapacity),
size(0),
front(-1),
rear(-1),
data(new T[capacity])
{
}

template <typename T, int desiredCapacity>
Queue<T, desiredCapacity>::Queue(int inDesiredCapacity):
capacity(inDesiredCapacity),
size(0),
front(-1),
rear(-1),
data(new T[capacity])
{
}

template <typename T, int desiredCapacity>
Queue<T, desiredCapacity>::~Queue()
{
	delete[] data;
}

template <typename T, int desiredCapacity>
int Queue<T, desiredCapacity>::Capacity() const
{
	return capacity;
}

template <typename T, int desiredCapacity>
int Queue<T, desiredCapacity>::Size() const
{
	return size;
}

template <typename T, int desiredCapacity>
void Queue<T, desiredCapacity>::ShowData()
{
	std::cout << "Show Queue: \n";
	std::cout << "Capacity: " << capacity << "\n";
	std::cout << "Size: " << size << "\n";
	std::cout << "<<<   ";
	
	for (int i = front, j = 0; j < size; ++i, ++j)
	{
		std::cout << data[i%capacity] << " ";
	}
	std::cout << "   <<<";
	std::cout << std::endl;
}

template <typename T, int desiredCapacity>
bool Queue<T, desiredCapacity>::IsEmpty() const
{
	return size == 0;
}

template <typename T, int desiredCapacity>
bool Queue<T, desiredCapacity>::IsFull() const
{
	return size == capacity;
}

template <typename T, int desiredCapacity>
void Queue<T, desiredCapacity>::Enqueue(T element)
{
	if (IsFull())
		return;

	if (front == -1)
		front = 0;

	rear = (rear + 1) % capacity;
	data[rear] = element;

	++size;
}

template <typename T, int desiredCapacity>
T Queue<T, desiredCapacity>::Dequeue()
{
	int indexDeq = front;
	front = (front + 1) % capacity;
	
	--size;
	
	return data[indexDeq];
}

template <typename T, int desiredCapacity>
T Queue<T, desiredCapacity>::Front() const
{
	return data[front];
}

template <typename T, int desiredCapacity>
T Queue<T, desiredCapacity>::Rear() const
{

	int indexRear = rear == 0 ? capacity - 1 : rear - 1;
	
	return data[indexRear];
}
